介绍

堆是一种特殊的树，满足如下两个条件

• 堆是一个完全二叉树
• 堆中的每个节点值都大于等于（小于等于）其子树中每个节点的值

堆的实现

完全二叉树天然适合使用数组来存储，节省空间，不需要左右节点的指针

• 左节点：2i
• 右节点：2i+1
• 父节点：i/2

---

0. 堆化操作
堆化（Heapify）即使堆重新符合堆特性的操作，分为自底向上和自顶向下两种

• 自底向上：从当前节点向上，依次进行比较和交换，直到满足堆特性
• 自顶向下：从当前节点向下，依次进行比较和交换，直到满足堆特性

1. 插入新元素
直接将新元素直接插入堆的末尾，从该元素开始执行自底向上的堆化操作

2. 删除（堆顶）元素
删除堆顶元素后，将堆的末尾元素放到堆顶，从该元素开始执行自顶向下的堆化操作

对于一个包含 n 个节点的完全二叉树，树的高度不会超过 logn，因此堆化的时间复杂度为 O(logn)，插入和删除的主要操作就是堆化，因此时间复杂度也为 O(logn)

删除任意一个元素：

• 假设删除任意元素 A，删除后，将最后的元素 B 交换至 A 的位置
• 根据 B 和 A 的大小关系，选择是向上堆化还是向下堆化

堆排序

堆排序是一种 O(nlogn) 的原地排序算法，主要分为两个步骤：建堆和排序

1. 建堆

这里假设要对数据从小到大进行排序，则建立一个最大堆

方法 1：从前向后处理数据
将数组按顺序插入堆中，最初假设数组中只包含一个元素，即下标为 1 的元素，接着按顺序插入下标 2 到 n 的数据即可

方法 2：从后向前处理数据
由于叶子节点均是符合要求的，因此从后向前找到第一个非叶子节点，从该节点开始到根节点，每个节点依次执行自顶向下的堆化操作即可

方法 2 对下标由 [n/2...1] 的节点进行了自顶向下的堆化，由此可以粗略估算时间复杂度为 O(nlogn)。实际上，如果进行更精确的计算，可以发现建堆的时间复杂度是 O(n)

// n/2 是第一个非叶子节点
private static void buildHeap(int[] a, int n) {
    for (int i = n/2; i >= 1; --i) {
    heapify(a, n, i);
    }
}

private static void heapify(int[] a, int n, int i) {
    while (true) {
        int maxPos = i;
        if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
        if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
        if (maxPos == i) break;
        swap(a, i, maxPos);
        i = maxPos;
    }
}

2. 排序

完成建堆操作后，此时数组已经是一个最大堆了，排序只需不断进行以下两个步骤即可得到有序数组

• 删除堆顶元素，将堆顶元素放至数组末尾（本质：堆顶元素与末尾元素进行交换）
• 对堆顶元素执行 Heapify 操作

复杂度与稳定性分析

• 稳定性：不稳定，排序过程中，交换可能会导致元素顺序改变

• 内存消耗：O(1)，是原地排序算法

• 执行效率：O(nlogn)，建堆操作复杂度 O(n)，排序操作复杂度 O(nlogn)

堆的应用

优先级队列

1. 合并有序小文件
100 个小文件，每个文件 100 MB，每个文件中存储有序字符串，希望合并成一个有序大文件

• 从 100 个文件中，各取第 1 个字符串，放入最小堆中
• 取出堆顶元素放入大文件中
• 接着从堆顶元素来源的文件取下一个字符串加入最小堆中，重复以上步骤

相比使用数组对 100 条字符串排序取最小，复杂度为 O(n)，使用优先队列复杂度只有 O(logn)

2. 高性能定时器 设计一个定时器，维护多个定时任务，到达特定触发时间则执行该任务

传统方案：定时器每隔 1 秒就扫描任务列表，检查是否与任务到达触发时间

改进方案：根据任务触发时间，将这些任务存储在优先队列中，定时器只需根据队首任务的执行时间，与当前时间比较，设置一个时间间隔，到达该时间间隔，则取出第一个任务执行，无需每秒轮询任务列表

Top K

1. 静态数据集合
维护一个大小为 K 的最小堆，遍历数组，将数组元素与堆顶元素比较（堆未满时，直接插入堆中）

• 如果比堆顶元素大，则把堆顶元素删除，将该元素插入堆中
• 如果比堆顶元素小，则不做处理，继续遍历数组

遍历数组需要 O(n)，堆化操作需要 O(logk)，则最坏时间复杂度为 O(nlogk)

2. 动态数据集合
与静态操作没有区别，每次有新元素插入，都与堆顶元素比较，执行相应操作即可

求中位数

用于求中位数的思想，同样适用于求其他如 25%，75% 分位数

1. 静态数据集合
求中位数可以直接利用排序或者借助 Kth Largest 算法

2. 动态数据集合
维护一个最大堆，一个最小堆，如果将数组从小到达排序，则

• 最大堆：存储数组前半部分数据，如果是奇数，存储前 n/2+1 个数据
• 最小堆：维护数组后半部分数据

由此，最小堆的堆顶元素大于最大堆的所有元素，最大堆的堆顶元素就是当前中位数

当有新数据需要处理时

• 新元素小于等于最大堆堆顶元素，插入最大堆
• 否则，插入最小堆

新元素插入完成后，可能需要调整堆元素数量，通过将一个堆的堆顶元素移动到另一个堆来维护约定